#ifndef __MATRIXGRAPH__
#define __MATRIXGRAPH__
#include <queue>
#include <iostream>
//the implementation of graph with adjacency matrix 
class MatrixGraph{
public:
	MatrixGraph(int vex_num, int arc_num, bool direction = false)
		:vex_num_(vex_num),arc_num_(arc_num),directed_(direction){}
	~MatrixGraph();
	void CreateGraph();
	void DeepFirstTraverse(int index);
	void BreadthFirstTraverse(int index);
private:
	int vex_num_;//node count
	int arc_num_;//arc count
	bool **matrix_;// the adjacency matrix
	bool * visited_;//whether visisted struct
	std::queue<int> iQue_;//the struct used to implement the breadth first traverse
	bool directed_;
};
MatrixGraph::~MatrixGraph(){
	delete [] visited_;
	for(int i = 0; i < vex_num_; ++i){
		delete [] matrix_[i];
	}
	delete [] matrix_;
}
void MatrixGraph::CreateGraph(){
	visited_ = new bool[vex_num_];
	matrix_ = new bool*[vex_num_];
	for(int i = 0; i < vex_num_; ++i){
		matrix_[i] = new bool[vex_num_];
	}
	//******************initialize************************ Begin
	for(int i = 0; i < vex_num_; ++i){
		visited_[i] = false;
	}
	for(int i = 0; i< vex_num_; ++i)
		for(int j = 0; j < vex_num_; ++j)
			matrix_[i][j] = false;
	//******************initialize************************ END
	for(int i = 0 ; i < arc_num_; ++i){
		std::cout <<"input the vertexes of the arcs :" << std::endl;
		int v1,v2;
		std::cin>>v1>>v2;
		matrix_[v1-1][v2-1] = true;
		if(!directed_) //if undirected graph
			matrix_[v2-1][v1-1] = true;
	}
}
void MatrixGraph::DeepFirstTraverse(int index){
	int p = index - 1;
	if(!visited_[p]){
		std::cout << index <<" ";
		visited_[p] = true;
	}
	for(int i = 0; i < vex_num_ ; ++i){
		if(!visited_[i] && matrix_[p][i]){
			DeepFirstTraverse(i+1);
		}
	}
}

void MatrixGraph::BreadthFirstTraverse(int index){
	int p = index - 1;
	if(!visited_[p]){
		std::cout<< index << " ";
		visited_[p] = true;
		iQue_.push(p);
	}
	for(;;){
		if(iQue_.empty()) break;
		int q = iQue_.front();
		for(int i = 0; i < vex_num_; ++i){
			if(!visited_[i] && matrix_[q][i]){
				std::cout<< i+1 << " ";
				visited_[i] = true;
				iQue_.push(i);
			}
		}
		iQue_.pop();
	}
}
#endif